package leetcode.drawing;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class dijkstra {
    public static HashMap<Node, Integer> dijkstra(Node head){
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(head, 0);
        HashSet<Node> selectedNodes = new HashSet<>();//已经锁住的节点
        Node minNode = getMinDAndUN(distanceMap, selectedNodes);
        while(minNode != null){
            int distance =  distanceMap.get(minNode);
            for(Edge edge : minNode.edges){
                Node toNode = edge.to;
                if(!distanceMap.containsKey(toNode)) distanceMap.put(toNode, distance + edge.weight);
                distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
            }
            selectedNodes.add(minNode);
            minNode = getMinDAndUN(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    public static Node getMinDAndUN(HashMap<Node, Integer> distanceMap, HashSet<Node> selectedNodes){
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for(Map.Entry<Node, Integer> entry : distanceMap.entrySet()){
            Node node = entry.getKey();
            int distance = entry.getValue();
            if(!selectedNodes.contains(node) && distance < minDistance){
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }
}
